import scala.annotation.tailrec

object Sorter extends App {

  private implicit val c = new Ordering[Int] {
    override def compare(x: Int, y: Int): Int = x.compareTo(y)
  }

  def combSort[T: Ordering](src: Seq[T]): (Seq[T], Int) = {
    val c = implicitly[Ordering[T]]
    var seq = src
    var gap = src.size
    val shrink = 1.25
    var swapped = true
    var n = 0
    while (gap > 1 || swapped) {
      if (gap > 1) gap = (gap / shrink).toInt
      var i = 0
      swapped = false
      while (i + gap < seq.size) {
        if (c.compare(seq(i), seq(i + gap)) > 0) {
          seq = seq.updated(i, seq(i + gap)).updated(i + gap, seq(i))
          swapped = true
        }
        i = i + 1
      }
      if (!(gap == 1 && !swapped)) n = n + 1
    }
    (seq, n)
  }

  def combSort2[T: Ordering](src: Seq[T]): (Seq[T], Int) = sort(src, src.size)

  @tailrec
  private def sort[T: Ordering](src: Seq[T], gap: Int, n: Int = 0): (Seq[T], Int) = {
    if (gap <= 1) {
      return (src, n)
    }
    val g = (gap / 1.25).toInt
    val (seq, swapped) = trySwap(src, 0, g)
    sort(seq, g, if (g != 1 || swapped) n + 1 else n)
  }

  @tailrec
  private def trySwap[T: Ordering](src: Seq[T], i: Int, gap: Int, swapped: Boolean = false): (Seq[T], Boolean) = {
    val c = implicitly[Ordering[T]]
    if (i + gap >= src.size) {
      return (src, swapped)
    }
    val result = if (c.compare(src(i), src(i + gap)) > 0) (src.updated(i, src(i + gap)).updated(i + gap, src(i)), true) else (src, swapped)
    trySwap(result._1, i + 1, gap, result._2)
  }
}
